#include <iostream>
//#include <stdlib.h>
using namespace std;
#define DEFAULT_SIZE 100

int kth_OfFive (int *array, int k, int lb, int ub)
{
    /*median of 5 is the 3rd smallest number*/
    int s1 = array[lb], s2 = array[lb + 1], s3 = array[lb + 2], i, tmp, size;
    size = ub - lb;
    if (s1 > s2) {
	tmp = s1;
	s1 = s2;
	s2 = tmp;
	if (size > 2 && s2 > s3) {
	    tmp = s2;
	    s2 = s3;
	    s3 = tmp;
	}
    } else if (size > 2 && s2 > s3) {
	tmp = s2;
	s2 = s3;
	s3 = tmp;
	if (s1 > s2) {
	    tmp = s1;
	    s1 = s2;
	    s2 = tmp;
	}
    }
    for (i = lb + 3; i < ub; i++) {
	if (array[i] < s1) {
	    tmp = s1;
	    s1 = array[i];
	    s3 = s2;
	    s2 = tmp;
	} else if (array[i] < s2) {
	    s3 = s2;
	    s2 = array[i];
	} else if (array[i] < s3)
	    s3 = array[i];
    }
    if (size == 1 || k == 1)
	return s1;
    else if (size == 2 || k == 2)
	return s2;
    else
	return s3;
}

int findMedian (int *array, int size, int k)
{
    int grps = 0, i = 0, *grpArr = NULL, M;
    int *A1, *A2, *A3;
    int s_a1 = 0, s_a2 = 0, s_a3 = 0;

    if (size == 1)
	return *array;
    if (size < 5)
	return kth_OfFive(array, k, 0, size);
    /*partition into groups of 5*/
    /*find median of each group*/
    grps = (!(size / 5)) ? size/5 : size/5 + 1;
    grpArr = (int*)malloc(sizeof(int) * grps);
    for (i = 0; i < grps; i++) {
	grpArr[i] = kth_OfFive(array, 3, i*5, (size >= (i*5) + 5) ? (i*5) + 5 : size);
    }
    /*find medain of medians*/
    M = findMedian(grpArr, grps, (grps%2 != 0)?(grps/2)+1:grps/2);
    /*partition into 3 subarrays, A1<M, A2=M, A3>M*/
    A1 = (int*)malloc(sizeof(int) * size);
    A2 = (int*)malloc(sizeof(int) * size);
    A3 = (int*)malloc(sizeof(int) * size);
    for (i = 0; i < size; i++) {
	if (array[i] < M)
	    A1[s_a1++] =  array[i];
	else if (array[i] > M)
	    A3[s_a3++] = array[i];
	else
	    A2[s_a2++] = array[i];
    }
    //free(array);
    if (k <= s_a1) {
	free(A2);
	free(A3);
	return findMedian(A1, s_a1, k);
    }
    else if (k > s_a1 + s_a2) {
	free(A1);
	free(A2);
	return findMedian(A3, s_a3, k - s_a1 - s_a2);
    }
    else {
	free(A1);
	free(A2);
	free(A3);
	return M;
    }
}

int main (int argc, char **argv)
{
    int *input = NULL;
    int *extra = NULL;
    int num, i = 0;
    char ans = 'n';
    int retVal;

    input = (int*)malloc(sizeof(int)*DEFAULT_SIZE);
    do {
	printf("\nelement?\t");
	scanf("%d", &num);
	input[i++] = num;
	printf("\twanna continue?\t");
	cin>>ans;
    } while (ans != 'n'&& ans != 'N');

    retVal = findMedian(input, i, (i%2 != 0)?(i/2)+1:i/2);
    printf("\n***Median of the input elements = %d\n", retVal);
    free(input);

    return 0;
}
